use std::collections::BinaryHeap;
use std::cmp::Ordering;

pub struct Solution;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode {
            next: None,
            val,
        }
    }

}

impl Ord for ListNode {
    fn cmp(&self, other: &Self) -> Ordering {
        self.val.cmp(&other.val)
    }
}

impl PartialOrd for ListNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Solution {
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        if lists.is_empty() {
            return None;
        }

        let mut heap = BinaryHeap::new();

        for mut val in lists.into_iter() {
            while let Some(v) = val {
                heap.push(Box::new(ListNode::new(v.val)));
                val = v.next;
            }
        }

        let len = heap.len();

        println!("len {}", len);

        match len {
            0 => None,
            1 => heap.pop(),
            _ => {
                let mut tail = heap.pop();
                while !heap.is_empty() {
                    let mut tmp = heap.pop().unwrap();
                    tmp.next = tail;
                    tail = Some(tmp);
                }

                tail
            }
        }
    }

    // pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
    //     let mut res = Box::new(ListNode::new(0));
    //     if lists.len() == 0 {
    //         return None;
    //     }
    //     let mut min_heap = BinaryHeap::new();
    //     for mut list in lists {
    //         if list.is_some() {
    //             min_heap.push(list.take()?); // Storing as Option<Box<ListNode>>
    //         }
    //     }
    //     let mut cur = &mut res;
    //     while !min_heap.is_empty() {
    //         cur.next = min_heap.pop(); // Return as Option<Box<ListNode>>
    //         cur = cur.next.as_mut()?;
    //         if cur.next.is_some() {
    //             min_heap.push(cur.next.take()?);
    //         }
    //     }
    //     res.next
    // }


}

pub fn merge_k_sorted_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
    Solution::merge_k_lists(lists)
}

fn main() {
   Solution::merge_k_lists(vec![]);
}


